package week_07;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 1499. 满足不等式的最大值
 * 给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。
 * 也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。
 * <p>
 * 请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
 * <p>
 * 题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
 * 输出：4
 * 解释：前两个点满足 |xi - xj| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。
 * 第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。* 没有其他满足条件的点，所以返回 4 和 1 中最大的那个。
 * 示例 2：
 * <p>
 * 输入：points = [[0,0],[3,0],[9,2]], k = 3
 * 输出：3
 * 解释：只有前两个点满足 |xi - xj| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。
 */
public class FindMaxValueOfEquation_1499 {

    public int findMaxValueOfEquation(int[][] points, int k) {
        //  维护单调队列的滑动窗口
        int n = points.length;
        int ans = Integer.MIN_VALUE;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 维护单调性,不满足出队列
            int[] cur = points[i];
            while (!deque.isEmpty() && cur[0] - points[deque.getFirst()][0] > k) deque.removeFirst();
            // 从队尾开始出对 比当前值大的数
            if (!deque.isEmpty())
                ans = Math.max(ans, cur[1] + cur[0] + points[deque.getFirst()][1] - points[deque.getFirst()][0]);
            while (!deque.isEmpty() && cur[1] - cur[0] > points[deque.getLast()][1] - points[deque.getLast()][0])
                deque.removeLast();
            deque.add(i);
        }
        return ans;
    }


    public int findMaxValueOfEquation_1(int[][] points, int k) {
        // 暴力搜索 时间复杂度不够 超时
        int n = points.length;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {

            for (int j = 0; j < i; j++) {
                if (points[i][0] - points[j][0] <= k) {
                    ans = Math.max(ans, points[i][1] + points[j][1] + points[i][0] - points[j][0]);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] arr = new int[][]{
                {1, 3},
                {2, 0},
                {5, 10},
                {6, -10}};
        FindMaxValueOfEquation_1499 test = new FindMaxValueOfEquation_1499();
        test.findMaxValueOfEquation(arr, 1);
    }
}
